package mess;

import java.util.Arrays;

public class LeeCode_56 {
    public static void main(String[] args) {
        int[][] intervals = new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] intervals2 = new int[][]{{2,3}, {4,5}, {6,7},{8,9},{1,10}};
        int[][] intervals3 = new int[][]{{2,3}, {5,5}, {2,2},{3,4},{3,4}};
        int[][] intervals4 = new int[][]{{4,6},{1,2},{1,3}};
        merge(intervals4);
    }

    private static int[][] merge(int[][] intervals) {
        int len = intervals.length;
        if (len == 1)
            return intervals;
        quickSort(intervals, 0, len - 1);
        int[][] res = new int[len][2];
        int index = 0;
        int max = intervals[0][1];
        res[0][0] = intervals[0][0];
        for (int i = 0; i < len - 1; i++) {
            max = Math.max(max, intervals[i][1]);
            int lMax = intervals[i][1];
            int rMin = intervals[i + 1][0];
            if (lMax <= max && rMin <= max) {
                continue;
            }
            if (lMax < rMin) {
                res[index][1] = max;
                res[index + 1][0] = rMin;
                index++;
                max = 0;
            }
        }
        max = Math.max(max, intervals[len - 1][1]);
        res[index][1] = max;
        res = Arrays.copyOfRange(res, 0, index + 1);
        return res;
    }

    private static void quickSort(int[][] intervals, int i, int j) {
        if (i >= j)
            return;
        int start = i;
        int end = j;
        int baseNum = intervals[i][0];
        while (start != end) {
            while (true) {
                if (start >= end || intervals[end][0] < baseNum)
                    break;
                end--;
            }
            while (true) {
                if (start >= end || intervals[start][0] > baseNum) {
                    break;
                }
                start++;
            }
            int temp = intervals[start][0];
            intervals[start][0] = intervals[end][0];
            intervals[end][0] = temp;

            temp = intervals[start][1];
            intervals[start][1] = intervals[end][1];
            intervals[end][1] = temp;
        }
        intervals[i][0] = intervals[start][0];
        intervals[start][0] = baseNum;

        int temp = intervals[i][1];
        intervals[i][1] = intervals[start][1];
        intervals[start][1] = temp;

        quickSort(intervals, i, start - 1);
        quickSort(intervals, start + 1, j);
    }
}
